package datastruct;

import org.junit.Test;

import java.util.Arrays;
import java.util.Stack;

public class NextGreaterElement496 {

    @Test
    public void testNextGreaterElementOfArray() {
        nextGreaterElementOfArray(new int[]{1, 2, 3, 4});
        nextGreaterElementOfArray(new int[]{1, 2, 4, 3});
        nextGreaterElementOfArray(new int[]{1, 3, 2, 4});
        nextGreaterElementOfArray(new int[]{1, 3, 4, 2});
        nextGreaterElementOfArray(new int[]{2, 4, 1, 3});
    }

    @Test
    public void nextGreaterElementOfCircle() {
        nextGreaterElementOfCircle(new int[]{1, 2, 3, 4});
        nextGreaterElementOfCircle(new int[]{1, 2, 4, 3});
        nextGreaterElementOfCircle(new int[]{1, 3, 2, 4});
        nextGreaterElementOfCircle(new int[]{1, 3, 4, 2});
        nextGreaterElementOfCircle(new int[]{2, 4, 1, 3});
    }

    // 单调栈只能针对单数组, 因为stack中的元素都来自单个nums, 每次需要吧nums[i]放进去
    // 单调栈的核心就是: 从后往前遍历; 拿栈顶与nums[i]比较, 如果小就出栈; 最后nums[i]要入栈.
    // 496官方解法只能针对没有重复元素的, 因为用了map, 不好.
    public int[] nextGreaterElementOfArray(int[] n) {
        int[] nextGreaters = new int[n.length];
        Stack<Integer> monoStack = new Stack<>();

        // 从右往左遍历
        for (int i = n.length-1; i >= 0; i--) {
            while (monoStack.size() > 0 && n[i] >= monoStack.peek()) {
                // 如果当前元素大于栈顶, 就把栈顶吃掉; 否则就退出循环
                monoStack.pop();
            }
            // 如果栈非空, 栈顶就是右侧第一个比它大的, 保存起来.
            nextGreaters[i] = monoStack.size() > 0 ? monoStack.peek() : -1;
            // 将当前元素入栈, 供后面循环
            // 这个栈从底向顶, 元素值递减, 元素的原下标也递减.
            monoStack.push(n[i]);
        }
        System.out.format("n: %s, nextGreaters: %s\n", Arrays.toString(n), Arrays.toString(nextGreaters));
        return nextGreaters;
    }

    // 503
    public int[] nextGreaterElementOfCircle(int[] nums) {
        int[] nextGreaters = new int[nums.length];
        Stack<Integer> monoStack = new Stack<>();

        // 以 n[length-1] 为中心将circle复制并拉直, 从 n[length-2] 开始往前更新栈
        for (int i = nums.length-2; i >= 0; i--) {
            while (monoStack.size() > 0 && nums[i] >= monoStack.peek()) {
                monoStack.pop();
            }
            monoStack.push(nums[i]);
        }
        
        // 从 n[length-1] 开始往前更新栈, 并计算 nextGreaters
        for (int i = nums.length-1; i >= 0; i--) {
            while (monoStack.size() > 0 && nums[i] >= monoStack.peek()) {
                monoStack.pop();
            }
            nextGreaters[i] = monoStack.size() > 0 ? monoStack.peek() : -1;
            monoStack.push(nums[i]);
        }
        System.out.format("n: %s, nextGreaters: %s\n", Arrays.toString(nums), Arrays.toString(nextGreaters));
        return nextGreaters;
    }
}
